package recursion

import problem.Problem

class Q95UniqueBinarySearchTreesII extends Problem {

  def generateTrees(n: Int): List[TreeNode] = {
    if (n == 0) Nil
    else generate(1, n).toList
  }

  def generate(s: Int, t: Int): Seq[TreeNode] = {
    if (s == t) Seq(new TreeNode(s))
    else if (s > t) Seq(null)
    else {
      (s to t).flatMap { i =>
        val left = generate(s, i - 1)
        val right = generate(i + 1, t)
        for (l <- left; r <- right) yield {
          val node = new TreeNode(i)
          node.left = l
          node.right = r
          node
        }
      }
    }
  }

  override def test(): Unit = {
    generateTrees(3).foreach(println)
  }
}
